package com.nlp.trie.experiment2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import com.google.common.collect.HashBasedTable;
import com.google.common.collect.Table;
import com.google.gson.Gson;


/**
 * HMM参数表
 * 实现了Viterbi算法
 */
public class HMM {
	
	/**
	 * 初始概率 
	 * <词性, 概率>
	 * initial.put("r",0.25)
	 * 如何计算初始概率
	 * 比如，假设一篇文章为：我/r 明天/n 去/v 北京/n 
	 * r出现1词， n出现2词，v出现1词
	 * 那么：
	 * r的初始概率为：0.25
	 * n的初始概率为：0.5
	 * v的初始概率为：0.25
	 */
	private Map<String,Double> initial = new HashMap<>();
	/**
	 * 转移概率
	 * <前一个词性, 后一个词性, 概率>
	 * transition.put("r","n",1.0);
	 * 如何计算转移概率
	 * 上题中
	 * r出现1词， n出现2词，v出现1词
	 * r n 出现1次，n v 出现1次， v n出现1次
	 * 所以 r n 的转移概率为：p(r,n)/p(r) = 1/1 = 1
	 * 转移概率表
	 *  	r	n	v
	 * r	0	1	0
	 * n	0	0	0.5
	 * v	0	1	0
	 */
	private Table <String,String,Double> transition = HashBasedTable.create();
	/**
	 * 发射概率
	 * <单词, 词性, 概率>
	 * emission.put("希望","n",0.01);
	 * 如何计算发射概率
	 * 假设一篇文章中：
	 * "希望"作为名词n出现5词，作为动词v出现7词，文章一共有名词500个，动词140ge
	 * 则 希望 n 的发射概率为 5/500 = 0.01
	 * 则 希望 v 的发射概率为 7/140 = 0.05
	 */
	private Table <String,String,Double> emission = HashBasedTable.create();

	@Override
	public String toString() {
		return initial.toString()+"\n"+transition.toString()+"\n"+emission.toString();
	}
	//get,set方法
	public void setInitial(Map<String, Double> initial) {
		this.initial = initial;
	}

	public void setTransition(Table<String, String, Double> transition) {
		this.transition = transition;
	}

	public void setEmission(Table<String, String, Double> emission) {
		this.emission = emission;
	}

	public Map<String, Double> getInitial() {
		return initial;
	}

	public Table<String, String, Double> getTransition() {
		return transition;
	}

	public Table<String, String, Double> getEmission() {
		return emission;
	}	
	

	/**
	 * 计算viterbi算法
	 * @param strs
	 * @return
	 */
	public String viterbi(String...strs){
		if(strs==null) {
			return null;
		}else if(strs.length==1) {
			Map<String, Double> map1 = emission.row(strs[0]);
			Map<String, Double> map2 = initial;
			Map<String, Double> viterbiMap = viterbiMap(map1,map2);
			return viterbiMin(viterbiMap).getKey();
		}else{
			Map<String, Double> map1 = emission.row(strs[0]);
			Map<String, Double> map2 = initial;
			Map<String, Double> viterbiMap = viterbiMap(map1,map2);
			String[] viterbi = viterbi(strs,1,viterbiMap);
			return Arrays.toString(viterbi);
		}
	}

	/**
	 * 递归回溯法寻找最佳可能
	 * @param strs
	 * @param i 当前第i个
	 * @param preMap  上一个的概率
	 * @return
	 */
	private String[] viterbi(String[] strs, int i, Map<String, Double> preMap) {
		Map<String,Double> nowMap = new HashMap<String,Double>();
		Map<String,String> preAndNow = new HashMap<String,String>();
		//寻找当前strs[i]所有可能情况的每一种最佳选择
		Map<String, Double> row = emission.row(strs[i]);
		for(Entry<String, Double> now : row.entrySet()){
			double min = Double.MAX_VALUE;
			String best = null;
			for(Entry<String, Double> pre:preMap.entrySet()){
				String s = strs[i];
				if (s.equals("部分")) {
					System.out.println(s);
				}
				double value = viterbiCaculate(s,now,pre);
				if(value<min){
					min = value;
					//前一个最好的词性
					best = pre.getKey();
				}
			}
			preAndNow.put(now.getKey(),best);
			nowMap.put(now.getKey(), min);
		}
		String []list = null;
		//最后一层
		Gson gson = new Gson();
		System.out.println(gson.toJson(nowMap));
		System.out.println(gson.toJson(preAndNow));
		if(i==strs.length-1){
			String key = viterbiMin(nowMap).getKey();
			list = new String[strs.length];
			list[i] = key;
			list[i-1] = preAndNow.get(key);
		}else{
			list = viterbi(strs,++i,nowMap);
			list[i-2]=preAndNow.get(list[i-1]);
		}
		return list;
	}
	/**
	 * 获取map里的最小值
	 * @param map
	 * @return
	 */
	private Entry<String,Double> viterbiMin(Map<String, Double> map) {
		List<Entry<String,Double>> list = new ArrayList<>(map.entrySet());
		Collections.sort(list,new Comparator<Entry<String,Double>>() {
			@Override
			public int compare(Entry<String, Double> o1, Entry<String, Double> o2) {
				return o1.getValue()>o2.getValue()?1:-1;
			}
		});
		return list.get(0);
	}

	/**
	 * 所有发射概率和初始概率相同key对应的value求对数后相加,返回一个新的map存储
	 * 一般用于求第一个数的viterbi算法的值
	 * @param map1  发射概率
	 * @param map2  初始概率
	 * @return
	 */
	private Map<String, Double> viterbiMap(Map<String, Double> map1, Map<String, Double> map2) {
		Map<String,Double> map = new HashMap<String,Double>();
		for(Entry<String,Double> entry:map1.entrySet()){
			double value = Math.log(entry.getValue())+Math.log(map2.get(entry.getKey()));
			map.put(entry.getKey(), -value);
		}
		return map;
	}
	/**
	 * 计算转移概率对数+发射概率对数+pre的值的和
	 * @param word
	 * @param now
	 * @param pre
	 * @return
	 */
	private double viterbiCaculate(String word, Entry<String, Double> now, Entry<String, Double> pre) {
		//转移概率 <前一个词性, 后一个词性, 概率>
		double t_prob = transition.get(pre.getKey(), now.getKey());
		return Math.log(t_prob)+Math.log(now.getValue())+pre.getValue();
	}

}
